www.gusucode.com > VC++ LZW算法压缩示例源码程序 > VC++ LZW算法压缩示例源码程序/code/LZW压缩算法源代码和示例程序/Lzwcode.cpp
//Download by http://www.NewXing.com #include "stdafx.h" #include "stdio.h" #include "memory.h" #include "assert.h" #include "lzwtable.h" #include "lzwcode.h" /* CDecodeBitArray */ CDecodeBitArray::CDecodeBitArray(DWORD dwInitWidth)// width in bit { m_pbBits=NULL; m_dwWidthInByte=0; m_dwTail=m_dwHead=0; if(dwInitWidth) InitBits(dwInitWidth); } CDecodeBitArray::~CDecodeBitArray() { ClearBits(); } void CDecodeBitArray::ClearBits(void) { if(m_pbBits) delete m_pbBits; m_dwTail=m_dwHead=0; m_dwWidthInByte=0; } void CDecodeBitArray::InitBits(DWORD dwInitWidth) { ClearBits(); DWORD dwLength=dwInitWidth/8; dwLength+=(dwInitWidth%8)?1:0; m_pbBits=new BYTE[dwLength]; m_dwHead=m_dwTail=0; m_dwWidthInByte=dwLength; } void CDecodeBitArray::InitBytes(DWORD dwInitWidth) { InitBits(dwInitWidth*8); } DWORD CDecodeBitArray::GetLeftBytes(void) { DWORD dwLeftBytes; DWORD dwLeftBits=GetLeftBits(); dwLeftBytes=dwLeftBits/8; dwLeftBytes+=(dwLeftBits%8)?1:0; return dwLeftBytes; } WORD CDecodeBitArray::RemoveBits(int iWidth) { WORD wGet=0; for(int i=iWidth-1;i>=0;i--) { if(RemoveFirstBit()) SET_BIT_1(wGet,i); } return wGet; } WORD CDecodeBitArray::RemoveFirstBit(void) { BYTE* pbFirstByte=m_pbBits+m_dwHead/8; BYTE bFirstByte=*pbFirstByte; WORD wGet=(CHECK_BIT_1(bFirstByte,7-m_dwHead%8))?1:0; m_dwHead++; return wGet; } BOOL CDecodeBitArray::AddBytes(BYTE* pbAdd,int iLength) { if(m_pbBits==NULL) return FALSE; Resort(); memcpy(m_pbBits+m_dwTail/8,pbAdd,iLength); m_dwTail+=8*(DWORD)iLength; return TRUE; } void CDecodeBitArray::Resort(void) {// because m_dwTail%8 always equal 0 if(m_dwHead<8) return; if(m_dwTail==m_dwHead) { m_dwTail=m_dwHead=0; return; } DWORD dwLength=GetLeftBytes(); DWORD dwHead=m_dwHead%8; DWORD dwMove=m_dwHead-dwHead; memcpy(m_pbBits,m_pbBits+(m_dwHead/8),(int)dwLength); m_dwHead=dwHead; m_dwTail-=dwMove; } /* class CEncodeBitArray */ CEncodeBitArray::CEncodeBitArray(DWORD dwInitWidth) { if(dwInitWidth==0) m_pbBits=NULL; else InitBits(dwInitWidth); } CEncodeBitArray::~CEncodeBitArray() { ClearBits(); } BOOL CEncodeBitArray::InitBits(DWORD dwInitWidth) { ClearBits(); assert(dwInitWidth); m_dwWidthInByte=dwInitWidth/8; m_dwWidthInByte+=(dwInitWidth%8)?1:0; m_pbBits=new BYTE[m_dwWidthInByte]; m_dwTail=0; return TRUE; } void CEncodeBitArray::ClearBits(void) { if(m_pbBits) delete m_pbBits; m_pbBits=NULL; } BOOL CEncodeBitArray::AddBits(WORD wAdd,int iWidth) { if(m_pbBits==NULL) return FALSE; for(int i=iWidth-1;i>=0;i--) { BYTE* pbByte=m_pbBits+m_dwTail/8; if(CHECK_BIT_1(wAdd,i)) SET_BIT_1(*pbByte,7-m_dwTail%8); else SET_BIT_0(*pbByte,7-m_dwTail%8); m_dwTail++; } return TRUE; } DWORD CEncodeBitArray::GetBytesWidth(void) { DWORD dwBytes=m_dwTail/8; dwBytes+=(m_dwTail%8)?1:0; return dwBytes; } int CEncodeBitArray::RemoveBytes(BYTE *pbGet,int iWant) { if(m_pbBits==NULL) return -1; int iTotal=(int)GetBytesWidth(); if(iWant>iTotal) iWant=iTotal; if(pbGet!=NULL) memcpy(pbGet,m_pbBits,iWant); memcpy(m_pbBits,m_pbBits+iWant,iTotal-iWant); int iTail=(int)m_dwTail; iTail-=iWant*8; if(iTail<0) iTail=0; m_dwTail=iTail; return iWant; } BOOL CLZWDecode::BeginLZWDecode(const DWORD dwLength,// the compressed length FUN_LZWDECODEGETNEXTBYTES pfunLZWGetNextBytes, FUN_LZWDECODEPUTNEXTBYTE pfunLZWPutNextByte, WORD wBuffer, FUN_LZWDECODEDBYTES pfunLZWDecodedBytes, DWORD dwBytesOnce) { m_dwDecodedByte=0; //printf("enter decode press a key\n"); BYTE *pbNewData=new BYTE[4000],*pbOutData=new BYTE[4000]; BYTE *pbBuffer=new BYTE[wBuffer]; BYTE bFirst; m_LZWTable.InitLZWTable(); int iBitWidth=9; m_iTotalEntry=LZW_BEGIN_ENTRY; BYTE* pbDecodedData; WORD wOld,wLastLen; m_baContain.InitBits((wBuffer+20)*8); int iR=0; DWORD dwRead=0; while(1) { if(m_baContain.GetLeftBytes()<5) { WORD wGetBytes=wBuffer; if((DWORD)wGetBytes+dwRead>dwLength) wGetBytes=(WORD)(dwLength-dwRead); if(wGetBytes!=0) { pfunLZWGetNextBytes(pbBuffer,wGetBytes); m_baContain.AddBytes(pbBuffer,wBuffer); dwRead+=wGetBytes; } } int iT=m_iTotalEntry+1; iT>>=9; iBitWidth=9; while(iT>0) { iT>>=1; iBitWidth++; } WORD wGet=m_baContain.RemoveBits(iBitWidth); if(wGet==LZW_END_CODE) { break; } if(wGet==LZW_CLEAR_CODE) { m_LZWTable.InitLZWTable(); wGet=m_baContain.RemoveBits(9); if(wGet==LZW_END_CODE) break; pbDecodedData=m_LZWTable.GetMatchData(wGet); WriteDecode(pbDecodedData, pfunLZWPutNextByte, pfunLZWDecodedBytes, dwBytesOnce); wOld=wGet; m_iTotalEntry=258; } else {// not clear pbDecodedData=m_LZWTable.GetMatchData(wGet); if(NULL!=pbDecodedData) {// in table bFirst=pbDecodedData[2]; WriteDecode(pbDecodedData, pfunLZWPutNextByte, pfunLZWDecodedBytes, dwBytesOnce); if(wOld!=LZW_CLEAR_CODE) {// not the first code be read in pbDecodedData=m_LZWTable.GetMatchData(wOld); wLastLen=*((WORD*)pbDecodedData); memcpy(pbNewData,pbDecodedData+2,wLastLen); pbNewData[wLastLen]=bFirst; m_LZWTable.AddToChild((WORD)m_iTotalEntry,pbNewData,wLastLen+1); m_iTotalEntry+=1; } wOld=wGet; } else { pbDecodedData=m_LZWTable.GetMatchData(wOld); bFirst=pbDecodedData[2]; wLastLen=*((WORD*)pbDecodedData); memcpy(pbOutData+2,pbDecodedData+2,wLastLen); pbOutData[wLastLen+2]=bFirst; *((WORD*)pbOutData)=wLastLen+1; WriteDecode(pbOutData, pfunLZWPutNextByte, pfunLZWDecodedBytes, dwBytesOnce); if(m_iTotalEntry>=4096) { int _j=0; } m_LZWTable.AddToChild((WORD)m_iTotalEntry,pbOutData+2,wLastLen+1); m_iTotalEntry+=1; wOld=wGet; } } //pbDecodedData=table.GetMatchData(wGet); //WORD wLen=*((WORD*)pbDecodedData); //pbDecodedData+=2; } delete pbNewData; delete pbOutData; delete pbBuffer; return dwRead==dwLength; } void CLZWDecode::WriteDecode(BYTE* pbWrite, FUN_LZWDECODEPUTNEXTBYTE pfunLZWPutNextByte, FUN_LZWDECODEDBYTES pfunLZWDecodedBytes, DWORD dwBytesOnce) { if(pbWrite==NULL) return; WORD wLength=*((WORD*)pbWrite); pbWrite+=2; for(DWORD i=0;i<wLength;i++) { pfunLZWPutNextByte(*pbWrite); pbWrite++; if((pfunLZWDecodedBytes!=NULL) && (dwBytesOnce) && (m_dwDecodedByte%dwBytesOnce==0)) { pfunLZWDecodedBytes(); } } m_dwDecodedByte+=wLength; } void CLZWDecode::EndLZWDecode(FUN_LZWDECODEPUTNEXTBYTE pfunLZWPutNextByte) { } /* CLZWEncode */ BOOL CLZWEncode::BeginLZWEncode(const DWORD dwLength, FUN_LZWENCODEGETNEXTBYTE pfunLZWGetNextByte, FUN_LZWENCODEPUTNEXTBYTES pfunLZWPutNextBytes, WORD wBufferLen, FUN_LZWENCODEDBYTES pfunLZWEncodedBytes, DWORD dwBytesOnce) { m_dwCompressedLength=0; int iBufferLen=wBufferLen; BYTE bGet; m_LZWTable.InitLZWTable();// init the entry table m_baContain.InitBits((iBufferLen+8)*8);// init the bit array m_baContain.AddBits(LZW_CLEAR_CODE,9);// add the first clear code /// below : begin the algorithm PLZWENCODEENTRY pCurrent=m_LZWTable.GetHead(); int iBitWidth; DWORD dwEncoded=0; for(DWORD i=0;i<dwLength;i++) {// for each byte if(!pfunLZWGetNextByte(bGet)) return FALSE; PLZWENCODEENTRY pChild=m_LZWTable.FindMatchChild(bGet,pCurrent); if(pChild) {// has found the continue pCurrent=pChild; } else {// not find write last code & add new entry iBitWidth=GetBitWidth(); WORD wW=pCurrent->wCode; m_baContain.AddBits(wW,iBitWidth);// add last code to buffer m_LZWTable.AddToChild(bGet,pCurrent);// add last code to table if(m_baContain.GetBytesWidth()>(DWORD)iBufferLen) { m_dwCompressedLength+=(DWORD)iBufferLen; pfunLZWPutNextBytes(m_baContain.GetBits(),iBufferLen); m_baContain.RemoveBytes(NULL,iBufferLen); } if(m_LZWTable.GetTableEntryNumber()>=(m_wMaxEntry-3)) { iBitWidth=GetBitWidth(); m_baContain.AddBits(LZW_CLEAR_CODE,iBitWidth); m_LZWTable.InitLZWTable(); } pCurrent=m_LZWTable.FindMatchChild(bGet,m_LZWTable.GetHead()); } dwEncoded++; if(pfunLZWEncodedBytes && dwEncoded==dwBytesOnce) { pfunLZWEncodedBytes(); dwEncoded=0; } } iBitWidth=GetBitWidth(); m_baContain.AddBits(pCurrent->wCode,iBitWidth);// add last code to buffer return TRUE; } void CLZWEncode::EndLZWEncode(FUN_LZWENCODEPUTNEXTBYTES pfunLZWPutNextBytes) { int iBitWidth=GetBitWidth(); m_baContain.AddBits(LZW_END_CODE,iBitWidth); m_dwCompressedLength+=m_baContain.GetBytesWidth(); pfunLZWPutNextBytes(m_baContain.GetBits(),(int)m_baContain.GetBytesWidth()); m_LZWTable.ClearLZWTable(); m_baContain.ClearBits(); }; int CLZWEncode::GetBitWidth(void) { int iTotal=(int)m_LZWTable.GetTableEntryNumber(); iTotal>>=9; int iBitWidth=9; while(iTotal>0) { iTotal>>=1; iBitWidth+=1; } return iBitWidth; }